package _09_高频题;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/lru-cache/
 *
 * @Author: haogege
 * @Date: 2021/9/3
 */
// 最近最少使用算法，使用map保存数据，因为的key-value, 如果使用另一种数据结果存储要淘汰的元素，者首先需要搜索，可能达不到o(1)
public class LRUCache1 {

    private Map<Integer, Node> containers;

    // 虚拟头结点, 首节点存放最近使用频繁数据
    private Node first;

    // 虚拟尾尾结点，尾部节点存放舍去元素
    private Node last;

    private int capacity;

    // 使用hash表，能达到O(1的时间复杂度)
    public LRUCache1(int capacity) {
        containers = new HashMap<>(capacity);
        first = new Node();
        last = new Node();
        first.next = last;
        last.prev = first;
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = containers.get(key);
        if (node == null) {
            return -1;
        } else {
            removeNode(node);
            // 添加首部
            addNodeToFirst(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        // 存放元素
        // 查看容器中是否存在
        Node node = containers.get(key);
        if (node == null) {
            int size = containers.size();
            // 不存在，新添加
            node = new Node(key, value);
            if (size == capacity) {
                // 删除最后元素
                removeNode(containers.remove(last.prev.key));
            }
            containers.put(key, node);
        } else {
            node.value = value;
            removeNode(node);
        }
        addNodeToFirst(node);
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addNodeToFirst(Node node) {
        node.next = first.next;
        first.next.prev = node;
        first.next = node;
        node.prev = first;
    }


    private static class Node {

        int key;

        int value;

        Node next;

        Node prev;


        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}
